W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Alphabet consists of initial letters of English alphabet. A positive integer called a weight is assigned to each letter of the alphabet. A weight of a word built from the letters of the alphabet is the sum of weights of all letters in this word. A language over an alphabet is any finite set of words built from the letters of this alphabet. A weight of a language is the sum of weights of all its words.
We say that the language is prefixless if for each pair of different words , from this language is not a prefix of . We want to find out what is the minimal possible weight of an -element, prefixless language over an alphabet .
Assume that , the weight of the letter — and the weight of the letter — . Then the weight of the word — . . The weight of the language — . The language is not prefixless, since the word is a prefix of . The lightest tree-element, prefixless language over the alphabet (assuming that weights of the letters are as before) is ; its weight is .
Write a program that:
In the first line of the standard input there are two positive integers and separated by a single space, (, ). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains positive integers separated by single spaces. Each of them is not greater than . The -th number is the weight of the -th letter.
In the first and only line of the standard output there should be written one integer — the weight of the lightest prefixless -element language over the alphabet .
For the input data:
3 2 2 5
the correct result is:
16
Task author: Wojciech Rytter.